package edu.assignment2;

import java.util.List;

import lpsolve.LpSolve;
import lpsolve.LpSolveException;
import edu.aa12.Edge;
import edu.aa12.Graph;

public class LpIntegerRelaxation {

	private Graph graph;

	public LpIntegerRelaxation(Graph graph) {
		this.graph = graph;
	}

	public double getSolution() {
		double result = 0;
		int numVertices = graph.getVertices();

		try {

			double[] vars = new double[numVertices * numVertices];

			LpSolve solver = LpSolve.makeLp(0, vars.length);

			double[] constr;

			for (int i = 0; i < graph.incidentEdges.length; i++) {
				List<Edge> edges = graph.incidentEdges[i];

				// constraints sum x_{ij} = 1.0
				constr = new double[numVertices * numVertices];
				for (Edge edge : edges) {
					vars[(i * numVertices) + edge.v] = graph.getLength(edge);
					constr[(i * numVertices) + edge.v] = 1.0;
				}
				solver.addConstraint(constr, LpSolve.EQ, 1.0);
			}

			// objective function sum d_{ij}
			solver.setObjFn(vars);

			// upper bound 1.0 constraints
			for (int i = 0; i < vars.length; i++) {
				constr = new double[vars.length];
				constr[i] = 1.0;
				solver.addConstraint(constr, LpSolve.LE, 1.0);
			}

			// subtour elimination constraints
			for (int i = 0; i < vars.length; i++) {
				constr = new double[vars.length];
				constr[i] = 1.0;
				for (int j = i + 1; j < vars.length - 1; j++) {
					constr[j] = 1.0;
					solver.addConstraint(constr, LpSolve.LE, j);
				}
			}
			for (int i = 0; i < vars.length; i++) {
				constr = new double[vars.length];
				for (int j = i + 1; j < vars.length - 1; j++) {
					constr[i] = constr[j] = 1.0;
					solver.addConstraint(constr, LpSolve.LE, j);
					constr = new double[vars.length];
				}
			}

			solver.setMinim();

			solver.setVerbose(LpSolve.IMPORTANT);

			solver.solve();

			result = solver.getObjective();

			solver.deleteLp();
		} catch (LpSolveException e) {
			e.printStackTrace();
		}
		return result;
	}
}
